package com.hy.study.practice.tree;

/**
 * 二叉树得练习
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        HiroTree hiroTree = new HiroTree();
        HiroNode root = new HiroNode(1, "宋江");
        HiroNode node1 = new HiroNode(2, "吴用");
        HiroNode node2 = new HiroNode(3, "鲁智深");
        HiroNode node3 = new HiroNode(4, "扈三娘");
        HiroNode node4 = new HiroNode(5, "武松");
        root.setLeft(node1);
        root.setRight(node2);
        node2.setLeft(node3);
        node2.setRight(node4);
        hiroTree.setRoot(root);
        System.out.println("前序遍历:");
        hiroTree.proOrder();
        System.out.println("中序遍历:");
        hiroTree.midOrder();
        System.out.println("后序遍历:");
        hiroTree.postOrder();
        System.out.println("前序遍历查找:" + hiroTree.preOrderSearch(5));
        System.out.println("中序遍历查找:" + hiroTree.infixOrderSearch(5));
        System.out.println("后序遍历查找:" + hiroTree.postOrderSearch(5));
        //  hiroTree.delete(3);
        hiroTree.deleteNode(3);
        System.out.println("------删除根节点之后右旋--");
        hiroTree.proOrder();
    }
}

class HiroTree {
    private HiroNode root;

    public HiroNode getRoot() {
        return root;
    }

    public void setRoot(HiroNode root) {
        this.root = root;
    }

    public HiroTree() {
    }

    public HiroTree(HiroNode root) {
        this.root = root;
    }

    /**
     * 前序遍历
     */
    public void proOrder() {
        this.root.preOrder();
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        this.root.midOrder();
    }

    /**
     * 后续遍历
     */
    public void postOrder() {
        this.root.postOrder();
    }

    /**
     * 前序遍历查找
     *
     * @param id
     * @return
     */
    public HiroNode preOrderSearch(int id) {
        if (root == null) {
            return null;
        } else {
            return root.preOrderSearch(id);
        }
    }

    /**
     * 中序遍历查找
     *
     * @param id
     * @return
     */
    public HiroNode infixOrderSearch(int id) {
        if (root != null) {
            return root.infixOrderSearch(id);
        } else {
            return null;
        }
    }

    /**
     * 后续遍历查找
     *
     * @param id
     * @return
     */
    public HiroNode postOrderSearch(int id) {
        if (root != null) {
            return root.postOrderSerach(id);
        } else {
            return null;
        }
    }

    /**
     * 删除某个节点，如果这个节点不是叶子节点，删除该节点所在的根节点的子树
     *
     * @param id
     */
    public void delete(int id) {
        if (root == null) {
            System.out.println("根节点为空，无法删除");
            return;
        }
        if (root.getId() == id) {
            root = null;
            return;
        }
        root.delete(id);
    }

    /**
     * 只删除节点，当该节点还有子节点或子树时，将子树右旋，即将左节点提上来
     *
     * @param id
     */
    public void deleteNode(int id) {
        if (root == null) {
            System.out.println("根节点为空，无法进行删除操作");
            return;
        }
        if (root.getId() == id) {
            HiroNode leftRightLast   = root.getRight();;
            root=root.getLeft();
            HiroNode temp = root;
            while (true) {
                HiroNode leftleftNode=temp.getLeft();
                temp.setLeft(leftleftNode);
                if (leftleftNode == null) {
                    temp.setRight(leftRightLast);
                    break;
                }
            }
            return;
        }
        root.deleteNode(id);
    }
}

/**
 * 树上每个节点信息
 */
class HiroNode {
    private int id;
    private String name;
    private HiroNode left;
    private HiroNode right;

    public HiroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public HiroNode() {
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HiroNode getLeft() {
        return left;
    }

    public void setLeft(HiroNode left) {
        this.left = left;
    }

    public HiroNode getRight() {
        return right;
    }

    public void setRight(HiroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HiroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前序遍历  根左右
     */
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历
     * 左根右
     */
    public void midOrder() {
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    /**
     * 后序遍历
     * 左右根
     */
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    /**
     * 前序遍历查找
     *
     * @param no
     * @return
     */
    public HiroNode preOrderSearch(int no) {
        if (this.getId() == no) {
            return this;
        }
        HiroNode result = null;
        if (this.getLeft() != null) {
            result = this.getLeft().preOrderSearch(no);
        }
        if (result != null) {
            return result;
        }
        if (this.getRight() != null) {
            result = this.getRight().preOrderSearch(no);
        }
        return result;
    }

    /**
     * 中序遍历查找
     *
     * @param id
     * @return
     */
    public HiroNode infixOrderSearch(int id) {
        HiroNode result = null;
        if (this.getLeft() != null) {
            result = this.getLeft().infixOrderSearch(id);
        }
        if (result != null) {
            return result;
        }
        if (this.getId() == id) {
            return this;
        }

        if (this.getRight() != null) {
            result = this.getRight().infixOrderSearch(id);
        }
        return result;
    }

    /**
     * 后序遍历查找
     *
     * @param id
     * @return
     */
    public HiroNode postOrderSerach(int id) {
        HiroNode result = null;
        if (this.getLeft() != null) {
            result = this.getLeft().postOrderSerach(id);
        }
        if (result != null) {
            return result;
        }
        if (this.getRight() != null) {
            result = this.getRight().postOrderSerach(id);
        }
        if (result != null) {
            return result;
        }
        if (this.getId() == id) {
            return this;
        }
        return result;
    }

    /**
     * 删除某个节点，如果这个节点不是叶子节点，删掉整个子树
     *
     * @param id
     */
    public void delete(int id) {
        if (this.getLeft() != null && this.getLeft().getId() == id) {
            this.setLeft(null);
            return;
        }

        if (this.getRight() != null && this.getRight().getId() == id) {
            this.setRight(null);
            return;
        }
        if (this.getLeft() != null) {
            this.getLeft().delete(id);
        }
        if (this.getRight() != null) {
            this.getRight().delete(id);
        }
    }

    /**
     * 删除节点 如果待删除的节点不是叶子节点，将左节点右旋，如果是叶子节点直接删除即可
     *
     * @param id
     */
    public void deleteNode(int id) {
        if (this.getLeft() != null && this.getLeft().getId() == id) {
            HiroNode temp = this.getLeft();
            HiroNode leftRightLast;
            while (true) {
                leftRightLast = temp.getRight();
                temp.setLeft(temp.getLeft());
                if (temp.getLeft() == null) {
                    temp.setRight(leftRightLast);
                    break;
                }
            }
            return;
        }
        if (this.getRight() != null && this.getRight().getId() == id) {
            this.setRight(this.getLeft().getLeft());
            HiroNode temp = this.getRight().getLeft();
            HiroNode leftRightLast;
            while (true) {
                leftRightLast = temp.getRight();
                temp.setLeft(temp.getLeft());
                if (temp.getLeft() == null) {
                    temp.setRight(leftRightLast);
                    break;
                }
            }
            return;
        }
        if (this.getRight() != null) {
            this.getRight().deleteNode(id);
        }
        if (this.getLeft() != null) {
            this.getLeft().deleteNode(id);
        }

    }


}